public class MergeBU {
    // 自底向上的归并排序
    public static void sort(Comparable[] a){
        Comparable[] aux = new Comparable[a.length];
        int N = a.length;
        for (int sz = 1; sz < N; sz = sz+sz){
            for (int lo = 0; lo < N - sz; lo += sz + sz){
                merge(aux, a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
            }
        }
    }

    private static void merge(Comparable[] aux, Comparable[] a, int lo, int mid, int hi){
        int i = lo;
        int j = mid + 1;
        System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
        for (int k = lo; k <= hi; k++){
            if (i > mid) {
                a[k] = aux[j++];
            }else if (j > hi) {
                a[k] = aux[i++];
            }else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
        }
    }

    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }

}
